package com.cab.pack.demo;

import com.alibaba.fastjson.JSON;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Comparator;
import java.util.List;
import java.util.stream.Collectors;

/**
 * @author lanyanhua
 * @date 2021/10/18 5:26 下午
 * @Description
 */
public class PackTestV2 {

    //标签
    private final List<Label> labels;
    //商品属性
    private List<Goods> goodsAttrs;
    //属性总量
    private int[] counts;

    public static void main(String[] args) {
        List<Label> labels = Arrays.asList(new Label("商品", 0),
                new Label("价值", 0),
                new Label("重量", 1011),
                new Label("体积", 1511));// 特征标签
        List<Goods> goodsAttrs = Arrays.asList(new Goods("a", 6, Arrays.asList(2, 10)),
                new Goods("b", 3, Arrays.asList(2, 5)),
                new Goods("c", 5, Arrays.asList(6, 2)),
                new Goods("d", 4, Arrays.asList(5, 6)),
                new Goods("e", 6, Arrays.asList(4, 4)));// 商品属性
        PackTestV2 pack = PackTestV2.of(labels, goodsAttrs);
        //总量
        long t = System.currentTimeMillis();
        System.out.println(t);
        Res res = pack.baseList();
        long t1 = System.currentTimeMillis();
        System.out.println(t1);
        System.out.println("耗时：" + (t1 - t));
        out(pack,res);
    }

    public static void out(PackTestV2 pack, Res res) {
        System.out.println("遍历次数：" + pack.count);
        //结果输出
        res.details = new ArrayList<>();
        for (int i = 0; i < res.num.length; i++) {
            if (res.num[i] == 0) {
                continue;
            }
            res.details.add(new Detail(pack.goodsAttrs.get(i), res.num[i]));
        }
        System.out.println(JSON.toJSONString(res));

        for (int i = 2; i < pack.labels.size(); i++) {
            PackTestV2.Label label = pack.labels.get(i);
            System.out.println("背包" + label.label + ":" + label.count);
        }
        System.out.println("可最大价值：" + res.getValue());
        System.out.println("名称\t数量\t价值\t明细总量");
        for (PackTestV2.Detail d : res.details) {
            PackTestV2.Goods goods = d.goods;
            System.out.print(goods.name + "\t" + d.number + "\t" + d.value + "\t");
            //明细
            for (int i = 0; i < goods.attrs.size(); i++) {
                System.out.print(pack.labels.get(i + 2).label + ":" + goods.attrs.get(i) * d.number + "\t");
            }
            System.out.println();
        }
    }

    private PackTestV2(List<Label> labels, List<Goods> goodsAttrs) {
        this.labels = labels;
        this.goodsAttrs = goodsAttrs;
    }

    public static PackTestV2 of(List<Label> labels, List<Goods> goodsAttrs) {
        PackTestV2 than = new PackTestV2(labels, goodsAttrs);
        // 总量
        than.counts = new int[labels.size() - 2];
        for (int i = 2; i < labels.size(); i++) {
            than.counts[i - 2] = labels.get(i).getCount();
        }
        //排序减少循环数量
        than.goodsAttrs = than.goodsAttrs.stream()
                .peek(i -> i.setMax(getMax(i.getAttrs(), than.counts)))
                .sorted(Comparator.comparing(Goods::getMax))
                .collect(Collectors.toList());
        return than;
    }

    public Res baseList() {
        return baseList(0, counts);
    }

    int count = 0;

    public Res baseList(int i, int[] counts) {
        int[] counts1 = counts.clone();
        if (i == this.goodsAttrs.size() - 1) {
            //最后一个，剩余量最大装满
            Goods goods = this.goodsAttrs.get(i);
            Res res = new Res();
            int max = getMax(goods.getAttrs(), counts1);
            res.num = new int[this.goodsAttrs.size()];
            res.num[i] = max;
            res.value = goods.value * max;
            return res;
        }
        //结果
        Res res = null;
        for (int i1 = i++; i1 < this.goodsAttrs.size(); i1++) {
            Goods goods = this.goodsAttrs.get(i1);
            //遍历数量 this.max[i1]可存放最大数量
            int max = getMax(goods.getAttrs(), counts1);
            for (int n = 0; n <= max; n++) {
                //减当前量
                if (n != 0) {
                    for (int c = 0; c < counts1.length; c++) {
                        counts1[c] = counts1[c] - goods.getAttrs().get(c);
                    }
                }
                //计算后面商品的数量
                Res res1 = baseList(i, counts1);
                if (n > 0) {
                    res1.num[i1] = n;
                    res1.value += n * goods.value;
                }
                //大于
                if (res == null || res1.value > res.value) {
                    res = res1;
                }
                count++;
            }
        }
        if (res == null) {
            res = new Res();
            res.num = new int[this.goodsAttrs.size()];
        }
        return res;
    }

    /**
     * 取当前商品最大数量
     *
     * @param attrs 属性
     * @param count 剩余数量
     * @return 最大值
     */
    public static int getMax(List<Integer> attrs, int[] count) {
        int max = -1;
        for (int i = 0; i < attrs.size(); i++) {
            int temp = count[i] / attrs.get(i);
            if (max == -1 || temp < max) {
                max = temp;
            }
        }
        return max;
    }

    public static class Label {
        // 标签
        private String label;
        // 总量
        private Integer count;

        public String getLabel() {
            return label;
        }

        public void setLabel(String label) {
            this.label = label;
        }

        public Integer getCount() {
            return count;
        }

        public void setCount(Integer count) {
            this.count = count;
        }

        public Label(String label, Integer max) {
            this.label = label;
            this.count = max;
        }
    }

    public static class Res {
        private List<Detail> details;
        private int[] num;
        private double value;

        public double getValue() {
            return value;
        }

        public void setValue(double value) {
            this.value = value;
        }

        public List<Detail> getDetails() {
            return details;
        }

        public void setDetails(List<Detail> details) {
            this.details = details;
        }
    }

    public static class Detail {
        // 商品
        private Goods goods;
        // 数量
        private int number;
        // 价值
        private double value;

        public Goods getGoods() {
            return goods;
        }

        public void setGoods(Goods goods) {
            this.goods = goods;
        }

        public int getNumber() {
            return number;
        }

        public void setNumber(int number) {
            this.number = number;
        }

        public double getValue() {
            return value;
        }

        public void setValue(double value) {
            this.value = value;
        }

        public Detail(Goods goods, int number) {
            this.goods = goods;
            this.number = number;
            this.value = goods.value * number;
        }
    }

    public static class Goods {
        // 名称
        private String name;
        // 价值
        private double value;
        // 属性
        private List<Integer> attrs;
        //可存放最大数量
        private int max;

        public int getMax() {
            return max;
        }

        public void setMax(int max) {
            this.max = max;
        }

        public String getName() {
            return name;
        }

        public void setName(String name) {
            this.name = name;
        }

        public double getValue() {
            return value;
        }

        public void setValue(double value) {
            this.value = value;
        }

        public List<Integer> getAttrs() {
            return attrs;
        }

        public void setAttrs(List<Integer> attrs) {
            this.attrs = attrs;
        }

        public Goods(String name, double value, List<Integer> attrs) {
            this.name = name;
            this.value = value;
            this.attrs = attrs;
        }
    }
}
